package com.hanxiaozhang.link.singlylink;

/**
 * 〈一句话功能简述〉<br>
 * 〈翻转单链表-万用公式〉
 * <p>
 * https://blog.csdn.net/weixin_46429290/article/details/124835823
 *
 * @author hanxinghua
 * @create 2022/5/30
 * @since 1.0.0
 */
public class ReverseSinglyNode {

    public static void main(String[] args) {

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        SinglyLink.whileNode(reverse(head));

        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        SinglyLink.whileNode(reverse1(head1));

    }

    /**
     * 该方法，好理解
     *
     * @param head
     * @return
     */
    public static Node reverse1(Node head) {

        Node pre = null;
        Node next = null;
        Node cur = head;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }


    public static Node reverse(Node head) {
        // 声明新的头结点
        Node newHead = new Node(-1);
        // 新头结点的后继节点指向head
        newHead.next = head;
        // 设置当前节点：newHead.next -> 即head
        Node cur = newHead.next;
        // 设置当前节点后继节点
        Node cur_next;

        // 循环判断
        while (cur != null && cur.next != null) {
            // 赋值cur_next
            cur_next = cur.next;
            // 另 cur.next = cur_next.next  -> 当前节点(cur)的后继指针 指向  cur_next的后继节点
            // 另  cur_next.next = newHead.next  -> cur_next的后继指针 指向 newHead的后继节点
            // 另  newHead.next = cur_next  -> newHead的后继指针 指向 cur_next
            // 完成两个元素位置调换
            cur.next = cur_next.next;
            cur_next.next = newHead.next;
            newHead.next = cur_next;
        }
        return newHead.next;
    }


}
